package io.zhengsh.vvip.leetcode.recall;

import java.util.ArrayList;
import java.util.List;

public class Q39_combination_sum {

    public static void main(String[] args) {

    }

    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> cob = new ArrayList<>();

            dsf(candidates, target, res, cob, 0);
            return res;
        }

        private void dsf(int[] candidates, int target, List<List<Integer>> res, List<Integer> cob, int i) {
            // 到达数组尾部退出
            if (candidates.length == i) {
                return;
            }
            // 求和成功添加到集合中
            if  (target == 0) {
                res.add(new ArrayList<>(cob));
                return;
            }
            dsf(candidates, target, res, cob, i + 1);
            if (target - candidates[i] >= 0) {
                cob.add(candidates[i]);
                dsf(candidates, target-candidates[i], res, cob, i);
                // 回溯
                cob.remove(cob.size() -1);
            }
        }
    }
}
